package com.test.demo;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Created by jl on 2019/7/25 0025
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 */
public class WordSplit1 {
    private static Boolean[] memo;

    public static void main(String[] args) {
        List<String> dict = Arrays.asList("le", "leet", "code");
        String s = "leqetcode";
//        memo = new Boolean[s.length()];
//        System.out.println(split(dict, s));
        System.out.println(dpImpl(dict, s));
    }

    private static boolean split(List<String> dict, String s) {
        HashSet<String> dictSet = new HashSet<>(dict);
        return doSplit(dictSet, s, 0);
    }

    private static boolean doSplit(HashSet<String> dictSet, String s, int start) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (dictSet.contains(s.substring(start, end)) && doSplit(dictSet, s, end)) {
                return memo[start] = true;
            }
        }
        return false;
    }

    // 动态规划实现
    private static boolean[] dp;

    private static boolean dpImpl(List<String> dict, String s) {
        HashSet<String> dictSet = new HashSet<>(dict);
        dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[j] && dictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
